//
// Created by 麻再挺 on 2021/12/20.
//

#include "avl_search.h"

/**
 * 左平衡
 * @param p 结点
 */
void LeftBalance(AvlTree *p);

/**
 * 右平衡
 * @param p 结点
 */
void RightBalance(AvlTree *p);

/**
 * 左旋
 * @param p 树
 */
void L_Rotate(AvlTree *p);

/**
 * 右旋
 * @param p 树
 */
void R_Rotate(AvlTree *p);

Status AVL_Insert(AvlTree *t, AvlElemType e, bool *taller) {
    // 如果本身为空树，则直接添加 e 为根结点
    if (!(*t)) {
        (*t) = malloc(sizeof(AvlNode));
        (*t)->bf = EH;
        (*t)->data = e;
        (*t)->lChild = NULL;
        (*t)->rChild = NULL;
        *taller = true;
    } else if (e == (*t)->data) {
        // 如果二叉排序树中已经存在 e ，则不做任何处理
        *taller = false;
        return 0;
    } else if (e < (*t)->data) {
        // 如果 e 小于结点 T 的数据域，则插入到 T 的左子树中
        // 如果插入过程，不会影响树本身的平衡，则直接结束
        if (!(AVL_Insert(&(*t)->lChild, e, taller))) {
            return 0;
        }
        // 判断插入过程是否会导致整棵树的深度 +1
        if (*taller) {
            // 判断根结点 T 的平衡因子是多少，由于是在其左子树添加新结点的过程中导致失去平衡，
            // 所以当 T 结点的平衡因子本身为 1 时，需要进行左子树的平衡处理，否则更新树中各结点的平衡因子数
            switch ((*t)->bf) {
                case LH:
                    LeftBalance(t);
                    *taller = false;
                    break;
                case EH:
                    (*t)->bf = LH;
                    *taller = true;
                    break;
                case RH:
                    (*t)->bf = EH;
                    *taller = false;
                    break;
            }
        }

    } else if (e > (*t)->data) {
        // 同样，当 e>T->data 时，需要插入到以 T 为根结点的树的右子树中，同样需要做和以上同样的操作
        if (!(AVL_Insert(&(*t)->rChild, e, taller))) {
            return 0;
        }
        if (*taller) {
            switch ((*t)->bf) {
                case LH:
                    (*t)->bf = EH;
                    *taller = false;
                    break;
                case EH:
                    (*t)->bf = RH;
                    *taller = true;
                    break;
                case RH:
                    RightBalance(t);
                    *taller = false;
                    break;
            }
        }
    }

    return 1;
}

void LeftBalance(AvlTree *p) {
    // 对以指针 T 所指向结点为根结点的二叉树作左子树的平衡处理，令指针 T 指向新的根结点
    AvlTree lc, rd;
    lc = (*p)->lChild;
    // 查看以 T 的左子树为根结点的子树，失去平衡的原因，如果 bf 值为 1 ，则说明添加在左子树为根结点的左子树中，
    // 需要对其进行右旋处理；反之，如果 bf 值为 -1，说明添加在以左子树为根结点的右子树中，需要进行双向先左旋后右旋的处理
    switch (lc->bf) {
        case LH:
            (*p)->bf = lc->bf = EH;
            R_Rotate(p);
            break;
        case RH:
            rd = lc->rChild;
            switch (rd->bf) {
                case LH:
                    (*p)->bf = RH;
                    lc->bf = EH;
                    break;
                case EH:
                    (*p)->bf = lc->bf = EH;
                    break;
                case RH:
                    (*p)->bf = EH;
                    lc->bf = LH;
                    break;
            }
            rd->bf = EH;
            L_Rotate(&(*p)->lChild);
            R_Rotate(p);
            break;
    }

}

void RightBalance(AvlTree *p) {
    // 右子树的平衡处理同左子树的平衡处理完全类似
    // lc 是平衡点, rd 是右孩子, *p 是不平衡点
    AvlTree lc, rd;
    lc = (*p)->rChild;
    switch (lc->bf) {
        case RH:
            (*p)->bf = lc->bf = EH;
            L_Rotate(p);
            break;
        case LH:
            rd = lc->lChild;
            switch (rd->bf) {
                case LH:
                    (*p)->bf = EH;
                    lc->bf = RH;
                    break;
                case EH:
                    (*p)->bf = lc->bf = EH;
                    break;
                case RH:
                    (*p)->bf = EH;
                    lc->bf = LH;
                    break;
            }
            rd->bf = EH;
            R_Rotate(&(*p)->rChild);
            L_Rotate(p);
            break;
    }
}

void L_Rotate(AvlTree *p) {
    // 对以 p 为根结点的二叉树做右旋处理，令 p 指针指向新的树根结点
    AvlTree rc = (*p)->rChild;
    (*p)->rChild = rc->lChild;
    rc->lChild = *p;
    *p = rc;
}

void R_Rotate(AvlTree *p) {
    // 对以 p 为根结点的二叉树做左旋处理，令 p 指针指向新的树根结点
    AvlTree lc = (*p)->lChild;
    (*p)->lChild = lc->rChild;
    lc->rChild = *p;
    *p = lc;
}

void InOrderAvlTraverse(AvlTree t) {
    if (t->lChild) {
        InOrderAvlTraverse(t->lChild);
    }
    printf("%d ", t->data);
    if (t->rChild) {
        InOrderAvlTraverse(t->rChild);
    }
}

bool Find_Node(AvlTree t, AvlElemType e, AvlTree *pos) {
    AvlTree pt = t;
    (*pos) = NULL;
    while (pt) {
        if (pt->data == e) {
            // 找到结点
            (*pos) = pt;
            return true;
        } else if (pt->data > e) {
            pt = pt->lChild;
        } else
            pt = pt->rChild;
    }
    return false;
}













